package com.shuang.stackAndQueue7;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequent {

    public int[] topKFrequent(int[] nums, int k) {
        /*对于队列：排在前面意味着往队头靠
         * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
         *                                从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点*/

        //利用小顶堆实现（维护k个 即排序k个即可 每次进入堆的元素判断是不是比堆中出现次数更高的是的话 弹出一个 再把这个加进来 每次弹出是从顶部弹出 所以小顶堆会把小的弹出去 留下的就是大的）

        //利用map集合对数组中每个数值出现的次数进行统计 key是数值 value为出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        //定义优先级队列（使用小顶堆） 利用数值出现的次数进行排序
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);

        //遍历map 将元素存放到优先级队列中（维护k个）
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            //队列中元素不足k个的时候直接加进去即可
            if (pq.size() < k) {
                pq.add(new int[] { entry.getKey(), entry.getValue() });
            } else {
                //队列中加完k个元素了 判断下一次来的元素是否是比队顶元素次数多的 是的话弹出再把他加进来 不是的话不用管
                if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[] { entry.getKey(), entry.getValue() });
                }
            }
        }

        //上述循环结束 小顶堆中就是k个维护好的元素了 将队列依次弹出 但是弹出是从队顶（堆的根 次数小的）开始弹 所以从后向前给数组加值返回
        //定义结果数组
        int[] res = new int[k];

        for (int i = k - 1; i >= 0; i--){
            res[i] = pq.poll()[0];
        }

        return res;

    }
}
